﻿#pragma once
#include <iostream>
#include <string.h>
#include<cstring>
using namespace std;
#include<stack>
#include<queue>
typedef enum { Link, Thread } NodeTag;



class TreeNode
{
    public:
    char data;              
    TreeNode* leftChild=NULL;    //左孩子
    TreeNode* rightChild = NULL;   //右孩子
    NodeTag lTag, rTag;     //线索Tag

    friend class MyTree;    //树类
public:
    TreeNode() = default;
    TreeNode(char, TreeNode*, TreeNode*, NodeTag, NodeTag);
    ~TreeNode() = default;

    void printNode();

};

class MyTree
{
public:
    TreeNode* root;        
    bool isThread;         
    TreeNode* pre;
    int flag = 0;
    int f = 0;
public:
    TreeNode* creattree(const char s[])
    {
        TreeNode* p = NULL;
        char ch = s[flag++];
        if (ch == '@')
        {
            return p;
        }
        else
        {
            p = new TreeNode;
            p->data = ch;
            p->leftChild = creattree(s);
            p->rightChild = creattree(s);
        }
        return p;
    }
    MyTree();               
    MyTree(const char[]);  
    MyTree(const MyTree&);  
    ~MyTree() = default;       

   TreeNode* copytree(const TreeNode* t, TreeNode* tt);
    void inthread(TreeNode* t);
    void preOrderTraverse();    
    void inOrderTraverse();     
    void postOrderTraverse();   
    int countLeaf();          
    int countHeight();
    int cheight(TreeNode* t)
    {
        if (t == NULL)
        {
            return 0;
        }
        else
        {
            int m = cheight(t->leftChild);
            int n = cheight(t->rightChild);
            return (m > n) ? m + 1 : n + 1;
        }
    }
    bool isThreadedTree();     
    bool inOrderThreading()
    {
        f = 1;
        if (root->leftChild == NULL)
            return false;
        root->lTag = Link;
        root->rTag = Thread;
        root->rightChild = root;
        if (root->leftChild == NULL)
        {
            root->leftChild = root;
        }
        else
        {
            TreeNode* t = root->leftChild;
            pre = root;
            inthread(t);
            pre->rTag = Thread;
            pre->rightChild = root;
            root->rightChild = pre;
        }
    }
    TreeNode& locateNode(const char&);  //结点定位
    TreeNode& preNode(const TreeNode&); //获取前驱结点
    TreeNode& nextNode(const TreeNode&);//获取后继结点

};


class HuffmanTree
{
private:
    int len;
    
public:
    struct point
    {
        int weight;
        int parent = -1;
        int lchild = -1;
        int rchild = -1;
    };
    point* tree;
    HuffmanTree(const int& n, int s[]);
   
    ~HuffmanTree()
    {
        delete[]tree;
    }
   

    void printHuffmanCodes()
    {
        struct str
        {
            point p;
            string s;
        };
        queue<str>que;
        str tep;
        tep.p = tree[len-1];
        tep.s = "";
        que.push(tep);
        while (!que.empty())
        {
            tep = que.front();
            que.pop();
            if (tep.p.lchild == -1 && tep.p.rchild == -1)
            {
                cout << tep.p.weight << ':' << tep.s << endl;
                
            }
            if (tep.p.rchild != -1)
            {
               
                int n1 = tep.p.rchild;
                str temp1;
                temp1.p = tree[n1];
                temp1.s = tep.s + '1';
                que.push(temp1);
            }
            if (tep.p.lchild != -1)
            {
                int n2 = tep.p.lchild;
                str temp2;
                temp2.p = tree[n2];
                temp2.s = tep.s + '0';
                que.push(temp2);
            }
        }
    }

};

